use std::i64;
use std::ptr::NonNull;
use std::str;

use data_structure::prelude::*;

#[derive(Copy, Clone, PartialEq)]
enum Token {
    TK_UNKNOWN,
    TK_OP_1,
    TK_OP_2,
    TK_NUM,
    TK_LPAR,
    TK_RPAR,
    TK_TRIM,
}

impl Default for Token {
    fn default() -> Self {
        Token::TK_UNKNOWN
    }
}

struct SyntaxTree<'a> {
    node: Option<NonNull<BNode<Vec<u8>>>>,
    sentence: &'a str,
}

impl SyntaxTree<'_> {
    #[inline]
    fn tokenize(b: u8) -> Token {
        match b {
            b' ' | b'\t' => Token::TK_TRIM,
            b'+' | b'-' => Token::TK_OP_1,
            b'*' | b'/' | b'%' => Token::TK_OP_2,
            b'0'..=b'9' => Token::TK_NUM,
            b'(' => Token::TK_LPAR,
            b')' => Token::TK_RPAR,
            _ => panic!("unknown token occurs: {}", b),
        }
    }

    #[inline]
    fn is_valid(l: Token, r: Token) -> bool {
        match (l, r) {
            (Token::TK_UNKNOWN, _) => true,
            (Token::TK_OP_1, Token::TK_NUM) | (Token::TK_OP_1, Token::TK_LPAR) => true,
            (Token::TK_OP_2, Token::TK_NUM) | (Token::TK_OP_2, Token::TK_LPAR) => true,
            (Token::TK_NUM, Token::TK_NUM) | (Token::TK_NUM, Token::TK_OP_1) => true,
            (Token::TK_NUM, Token::TK_OP_2) | (Token::TK_NUM, Token::TK_RPAR) => true,
            (Token::TK_LPAR, Token::TK_NUM) | (Token::TK_LPAR, Token::TK_OP_1) => true,
            (Token::TK_RPAR, Token::TK_OP_1) | (Token::TK_RPAR, Token::TK_OP_2) => true,
            _ => false,
        }
    }

    fn analysis(node: NonNull<BNode<Vec<u8>>>) -> i64 {
        unsafe {
            if (*node.as_ptr()).is_leaf() {
                match i64::from_str_radix(str::from_utf8(&(*node.as_ptr()).value()).unwrap(), 10) {
                    Ok(val) => val,
                    Err(_) => 0i64,
                }
            } else {
                let lhd = Self::analysis((*node.as_ptr()).left().unwrap());
                let rhd = Self::analysis((*node.as_ptr()).right().unwrap());
                match (*node.as_ptr()).value()[0] {
                    b'+' => lhd + rhd,
                    b'-' => lhd - rhd,
                    b'*' => lhd * rhd,
                    b'/' => lhd / rhd,
                    b'%' => lhd % rhd,
                    tok => panic!("unexpected token: {}", tok),
                }
            }
        }
    }

    #[inline]
    fn initialize(&mut self) {
        let mut bytes = self.sentence.bytes();
        let mut ident = Vec::<u8>::new();
        let mut node: NonNull<BNode<Vec<u8>>> = Box::leak(BNode::create(Vec::new())).into();
        let mut elem: Option<NonNull<BNode<Vec<u8>>>> = None;
        let (mut last_op, mut last_tok) = (Token::TK_UNKNOWN, Token::TK_UNKNOWN);
        let mut stack_subroot = Stack::<Table<DNode<NonNull<BNode<Vec<u8>>>>>>::new();
        let mut stack_last_op = Stack::<List<Token>>::new();
        while let Some(b) = bytes.next() {
            let tok = Self::tokenize(b);
            if tok == Token::TK_TRIM {
                continue;
            }
            if Self::is_valid(last_tok, tok) {
                last_tok = tok;
            } else {
                panic!("parse failed because of unexpected character sequence");
            }
            match tok {
                Token::TK_NUM => ident.push(b),
                Token::TK_OP_1 | Token::TK_OP_2 => unsafe {
                    let rhd = Box::leak(BNode::create(Vec::new())).into();
                    if last_op == Token::TK_OP_2 && tok == Token::TK_OP_1 {
                        let lhd = (*node.as_ptr()).parent().unwrap();
                        if let Some(abs_elem) = elem {
                            (*lhd.as_ptr()).set_right(Some(abs_elem));
                            (*abs_elem.as_ptr()).set_parent(Some(lhd));
                            Box::from_raw(node.as_ptr());
                            elem = None;
                        } else {
                            (*node.as_ptr()).set_value(ident);
                            ident = Vec::<u8>::new();
                        }
                        let par: NonNull<BNode<Vec<u8>>> = Box::leak(BNode::create(vec![b])).into();
                        if let Some(lhd_par) = (*lhd.as_ptr()).parent() {
                            (*par.as_ptr()).set_parent(Some(lhd_par));
                            (*lhd_par.as_ptr()).set_right(Some(par));
                        }
                        (*lhd.as_ptr()).set_parent(Some(par));
                        (*par.as_ptr()).set_left(Some(lhd));
                        (*par.as_ptr()).set_right(Some(rhd));
                        (*rhd.as_ptr()).set_parent(Some(par));
                    } else {
                        let lhd: NonNull<BNode<Vec<u8>>> = match elem {
                            Some(abs_elem) => {
                                elem = None;
                                abs_elem
                            }
                            None => {
                                let id = ident.clone();
                                ident = Vec::<u8>::new();
                                Box::leak(BNode::create(id)).into()
                            }
                        };
                        (*node.as_ptr()).set_left(Some(lhd));
                        (*lhd.as_ptr()).set_parent(Some(node));
                        (*node.as_ptr()).set_value(vec![b]);
                        (*node.as_ptr()).set_right(Some(rhd));
                        (*rhd.as_ptr()).set_parent(Some(node));
                    }
                    node = rhd;
                    last_op = tok;
                },
                Token::TK_LPAR => {
                    stack_last_op.push(last_op);
                    stack_subroot.push(node);
                    last_op = Token::TK_UNKNOWN;
                    node = Box::leak(BNode::create(Vec::new())).into();
                }
                Token::TK_RPAR => unsafe {
                    if let Some(abs_elem) = elem {
                        if let Some(parent) = (*node.as_ptr()).parent() {
                            (*parent.as_ptr()).set_right(Some(abs_elem));
                            (*abs_elem.as_ptr()).set_parent(Some(parent));
                            Box::from_raw(node.as_ptr());
                        }
                        node = abs_elem;
                    } else {
                        (*node.as_ptr()).set_value(ident);
                        ident = Vec::<u8>::new();
                    }
                    if let (Some(op), Some(n)) = (stack_last_op.pop(), stack_subroot.pop()) {
                        last_op = op;
                        while let Some(p) = (*node.as_ptr()).parent() {
                            node = p;
                        }
                        elem = Some(node);
                        node = n;
                    } else {
                        panic!("parens are not pairwise");
                    }
                },
                _ => {}
            }
        }
        unsafe {
            if let Some(abs_elem) = elem {
                if let Some(parent) = (*node.as_ptr()).parent() {
                    (*parent.as_ptr()).set_right(Some(abs_elem));
                    (*abs_elem.as_ptr()).set_parent(Some(parent));
                    Box::from_raw(node.as_ptr());
                }
                node = abs_elem;
            } else {
                (*node.as_ptr()).set_value(ident);
            }
            while let Some(p) = (*node.as_ptr()).parent() {
                node = p;
            }
        }
        self.node = Some(node);
    }
}

impl<'a> SyntaxTree<'a> {
    #[inline]
    pub fn parse(target: &'a str) -> Self {
        let mut tree = Self {
            node: None,
            sentence: target,
        };
        tree.initialize();
        tree
    }
    #[inline]
    pub fn solve(&'a self) -> Option<String> {
        if let Some(root) = self.node {
            Some(Self::analysis(root).to_string())
        } else {
            None
        }
    }
}

#[test]
fn calculator() {
    let sentence = SyntaxTree::parse("(5 + 3) + (7 * (8 + 2) - 4) / 2 + 1");
    assert_eq!(String::from("42"), sentence.solve().unwrap());
}
